package org.algorithm.biubiu.wheel_1.字符串;

import java.util.ArrayList;
import java.util.List;

/**
 * 给定一个字符串 s ，请将 s 分割成一些子串，使每个子串都是 回文串 ，返回 s 所有可能的分割方案。
 *
 * 回文串是正着读和反着读都一样的字符串。
 *
 * 
 *
 * 示例 1：
 *
 * 输入：s = "google"
 * 输出：[["g","o","o","g","l","e"],["g","oo","g","l","e"],["goog","l","e"]]
 * 示例 2：
 *
 * 输入：s = "aab"
 * 输出：[["a","a","b"],["aa","b"]]
 * 示例 3：
 *
 * 输入：s = "a"
 * 输出：[["a"]]
 *
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/M99OJA
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 */
public class 分割回文子字符串 {
    char[] arr;
    List<List<String>> list =   new ArrayList();

    public String[][] partition(String s) {

        arr = s.toCharArray();
        backTracking(0);
        return toArray(list);
    }

    List<String> ele=new ArrayList();
    public void backTracking(int index){
        if(index==arr.length){
            list.add(new ArrayList(ele));
            return;
        }

        for(int i = index; i<arr.length;i++){
            String s =  getData(index,i);
            System.out.println(index +"---"+i);
            if(ishuiwen(s)){
                ele.add(s);
                backTracking(i+1);
                ele.remove(ele.size()-1);
            }

        }

    }

    public String getData(int index,int i){
        if(index==i){
            return String.valueOf(arr[i]);
        }

        StringBuilder sb = new StringBuilder();
        for(int j = index; j<=i;j++){
            sb.append(arr[j]);
        }
        return sb.toString();

    }

    public boolean ishuiwen(String ele){
        int start = 0,end=ele.length()-1;
        while(start<=end ){
            if(ele.charAt(start)!=ele.charAt(end)){
                return false;
            }
            start++;
            end--;
        }
        return true;

    }


    public String[][] toArray(List<List<String>> res){
        String[][] resArr = new String[res.size()][];
        for(int i = 0; i < res.size(); i++){
            List<String> list = res.get(i);
            resArr[i] = list.toArray(new String[list.size()]);
        }
        return resArr;
    }

}
